這是一題單向鏈結串列反轉的題目,運用指標的算法,目標是將原本的鏈結串列倒序排列,此演算有使用到一個 while 迴圈,則時間複雜度估 O(n)
,這裡有 JAVA 和 Python 的寫法。
Given the
head
of a singly linked list, reverse the list, and return the reversed list.
給定一個
head
單向鏈結串列,反轉這個串列,且回傳反轉過後的這個串列。
題目連結:https://leetcode.com/problems/reverse-linked-list/description/
The number of nodes in the list is the range [0, 5000]
.5000 <= Node.val <= 5000
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Input: head = [1,2]
Output: [2,1]
Input: head = []
Output: []
鏈結串列的題目,簡單想像是在處理節點的位置,資料先放一邊別去裡他。
這裡設定三個指標分別是指向 null 的 (指標一)、指向當前 head 的 (指標二)、輔助指標 nextNode (指標三)。
- 設定好三個指標後
- 把當前的
curr.next
掛在輔助指標 nextNode 上 (確保在反轉的過程中不會失去原始下一個節點的位置)- 掛完之後把當前節點
curr.next
指向 prev (此時指針已反轉了)- 接下來移動指針 prev 到 curr
- 將 curr 掛在 nextNode (剛剛保存的原始下一個節點的位置)
- 以上邏輯循環到最後,當 curr 移動到 null 時則停止迴圈 (鏈結串列的末端節點一定會指向 null)
[補充] curr.next
同等於 curr → link
(指向下一個節點的意思)
class Solution {
public ListNode reverseList(ListNode head) {
ListNode curr = head; // 當前指標 (指標一)
ListNode prev = null; // 空集合指標 (指標二)
// 檢查確定鏈結串列裡有資料
while (curr != null) {
ListNode nextNode = curr.next; // 輔助指標 (指標三),指向下一個節點 (資料暫存在輔助指標內)
curr.next = prev; // 將 curr 的 next 指針指向 prev,(將當前節點的指針方向反轉)
prev = curr; // 更新指針指向:將 prev 設為 curr
curr = nextNode; // curr 設為 nextNode
}
return prev;
}
}
使用了和 Java 一樣的邏輯執行,換成 Python 的寫法。
(Python 中不需要再宣告一個額外的變數來存儲原始的鏈結串列)
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None # 空集合指標 (指標一)
while head:
nextNode = head.next # 輔助指標 (指標二)
head.next = prev # 反轉
prev = head # 移動指標
head = nextNode # 掛回去原本的鏈結串列
return prev
Language | Runtime | Memory |
---|---|---|
Java | 0ms | 41.8MB |
Python | 53ms | 17.9MB |
(新手上路,如有錯誤請友善告知,感謝)
Blog
https://chris81051.github.io/2023/06/29/LeetCode-206-Reverse-Linked-List-Java-Python/
有分享技術文章、科技新聞、日常生活,歡迎一起討論